package org.laizili.solution.nowcodertop101.list;

import org.laizili.structure.list.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&sfm=html&channel=nowcoder">链表的奇偶重排</a>
 * <p>
 * tags:链表
 */
public class BM14 {
    private static class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param head ListNode类
         * @return ListNode类
         */
        public ListNode oddEvenList(ListNode head) {
            // write code here
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode cursor = head;
            ListNode pred = dummy;
            ListNode tail = dummy;
            while (cursor != null) {
                pred.next = cursor.next;
                ListNode tmp = cursor;
                pred = cursor.next;
                if (pred != null)
                    cursor = cursor.next.next;
                else cursor = null;
                tmp.next = tail.next;
                tail.next = tmp;
                tail = tmp;
            }
            return dummy.next;
        }
    }
}
